package tree

type SegmentTree struct {
	Tree []int
	n    int
}

func BuildSegmentTree(arr []int) SegmentTree {
	var st SegmentTree = SegmentTree{n: len(arr)}
	n := st.n
	st.Tree = make([]int, 2*n)
	for i := n; i < 2*n; i++ {
		st.Tree[i] = arr[i-n]
	}
	for i := n - 1; i > 0; i-- {
		st.Tree[i] = st.Tree[2*i] + st.Tree[2*i+1] // merge
	}
	return st
}

func (st *SegmentTree) Update(i, value int) {
	n := st.n
	i += n
	st.Tree[i] = value
	for i > 1 {
		i /= 2
		st.Tree[i] = st.Tree[2*i] + st.Tree[2*i+1] // merge
	}
}

func (st *SegmentTree) Search(left, right int) int {
	n := st.n
	left += n
	right += n
	result := 0

	for left < right {
		if left%2 == 1 {
			result += st.Tree[left]
			left++
		}
		if right%2 == 1 {
			right--
			result += st.Tree[right]
		}
		left /= 2
		right /= 2
	}
	return result
}
